import java.util.*;
//********************************************************************
// KjedetBinærSøkeTre.java        
//
//********************************************************************


class KjedetBinærSøkeTre <T extends Comparable> {
 
    private int antall;
    private BinærTreNode<T> rot; 

                                 

   /******************************************************************
     Oppretter et tomt binært søketre.
   ******************************************************************/
   public KjedetBinærSøkeTre() 
   {
     antall = 0;
     rot    = null;
   }
   
   /******************************************************************
     Oppretter et binært søketre med en node..
   ******************************************************************/
   public KjedetBinærSøkeTre (T element) 
   {
      antall = 1;
      rot    = new BinærTreNode<T> (element);
   }
   
         
    
    /*****************************************************************
     Returnerer sann hvis dette binære trett er tomt og usann ellers.
   *****************************************************************/
   public int antall() 
   {
      return antall;
   }
   
   
   /*****************************************************************
     Returnerer sann hvis dette binære treet er tom og usann ellers.
   *****************************************************************/
   public boolean erTom() 
   {
      return (antall == 0);
   }

   /******************************************************************
     Legger det spesifiserte elementet på passende plass i dette binære 
     søketreet. Like elementer blir lagt til høyre.
     ******************************************************************/
   public void leggTilElement (T element) 
   {
      BinærTreNode<T> temp = new BinærTreNode<T> (element);
      if (erTom())
         rot = temp;
      else 
      {
         BinærTreNode<T> aktuell = rot;
         boolean lagtTil = false;

         while (!lagtTil) 
         {
            if (element.compareTo(aktuell.hentElement()) < 0) 
          
            {
               if (aktuell.hentVenstre() == null) 
               {
                  aktuell.settVenstre(temp);
                  lagtTil = true;
               } 
               else
                  aktuell = aktuell.hentVenstre();
            }
            else
            {
               if (aktuell.hentHøyre() == null) 
               {
                  aktuell.settHøyre(temp);;
                  lagtTil = true;
               } 
               else
                  aktuell = aktuell.hentHøyre();
            }
         }
      }
      
      antall++;
   }
   
   /**********************************************************************
     Legger det spesifiserte elementet på passande plass i BS-treet.
     Like elementer blir lagt til høgre. Bruk av rekursiv hjelpemetode.
     ********************************************************************/
   public void leggTilElement1(T element){
		rot = leggTilRek(rot, element);
		antall++;
	}
	
	private  BinærTreNode<T> leggTilRek(BinærTreNode<T> p, T element){
	// Den rekursive hjelpemetoden
	
		if (p==null){	// Tomt (under-)tre, lag node
			BinærTreNode<T> ny = new BinærTreNode<T>(element);
			return ny;
		}else if (element.compareTo(p.hentElement())<0){
			p.settVenstre(leggTilRek(p.hentVenstre(), element));
			return p;
		}else{
			p.settHøyre(leggTilRek(p.hentHøyre(), element)); // Ev. like til høgre
			return p;
		}
	}
	
   public T fjernMin() 
   {
      T resultat = null;

      if (!erTom())
      {
         if (rot.hentVenstre() == null) 
         {
            resultat = rot.hentElement();
            rot = rot.hentHøyre();
         }
         else 
         {
            BinærTreNode<T> foreldre = rot;
            BinærTreNode<T> aktuell = rot.hentVenstre();
            while (aktuell.hentVenstre() != null) 
            {
               foreldre = aktuell;
               aktuell  = aktuell.hentVenstre();
            }
            resultat =  aktuell.hentElement();
            foreldre.settVenstre(aktuell.hentHøyre());
         }

         antall--;
      }
 
      return resultat;
   }//

   /******************************************************************
     Fjerner noden med største verdi fra dette binære søketreet. 
   ******************************************************************/
   public T fjernMaks()
   {
      T resultat = null;

      if (!erTom()){
               
          if (rot.hentHøyre() == null) 
         {
            resultat =  rot.hentElement();
            rot = rot.hentVenstre();
         }
         else 
         {
            BinærTreNode<T> foreldre = rot;
            BinærTreNode<T> aktuell = rot.hentHøyre();
            while (aktuell.hentHøyre()!= null) 
            {
               foreldre = aktuell;
               aktuell = aktuell.hentHøyre();
            }
            
            resultat =  aktuell.hentElement();
            foreldre.settHøyre(aktuell.hentVenstre());
         }

         antall--;
      }

      return resultat;
   }//

   /******************************************************************
     Returnerer det minste elementet i dette binære søketreet. 
   ******************************************************************/
     public T finnMin(){
   
      T resultat = null;

      if (!erTom())        
      {
         BinærTreNode<T> aktuell = rot;
        
         while (aktuell.hentVenstre()!= null)
            aktuell = aktuell.hentVenstre();
       
         resultat = aktuell.hentElement();
      }

      return resultat;
   }//

   /******************************************************************
     Returnerer det største elementet i dette binære søketreet. 
   ******************************************************************/
   public T finnMaks() {
      T resultat = null;

      if (!erTom()){
     
         BinærTreNode<T> aktuell = rot;
      
         while (aktuell.hentHøyre() != null)
                 aktuell = aktuell.hentHøyre();
         
         resultat = aktuell.hentElement();
      }
 
      return resultat;
   }//

   /**********************************************************************
     Returnerer en fereranse til det spesifiserte elementet hvis det fins
     i dette binære treet ellers returneres null.
  / ***********************************************************************/
   public T finn (T element)  
   {
      BinærTreNode<T> aktuell = rot; 
      BinærTreNode<T> temp = aktuell;
      T resultat = null;
      
      if (!(aktuell.hentElement().equals(element)) && (aktuell.hentVenstre() !=null)&&
            (((Comparable)aktuell.hentElement()).compareTo(element) > 0))
         aktuell = finnIgjen(element, aktuell.hentVenstre());
              
       else if (!(aktuell.hentElement().equals(element)) && (aktuell.hentHøyre() != null)) 
         aktuell = finnIgjen( element, aktuell.hentHøyre());
      
      if (!(aktuell.hentElement().equals(element)))
          resultat = null;
      else     
           resultat = aktuell.hentElement();
           
      return resultat;
   }

   /************************************************************************
     Returnerer en referanse til det speisfiserte elemnetet hvis det fins
     i dette binære treet eller returneres null.  
  / ***********************************************************************/
   private BinærTreNode<T> finnIgjen (T element, BinærTreNode<T> neste) 
   {
      BinærTreNode<T> aktuell = neste;
      
      if (!(neste.hentElement().equals(element)) && (neste.hentVenstre() !=null) &&
            (((Comparable)neste.hentElement()).compareTo(element) > 0))
         neste = finnIgjen(element, neste.hentVenstre());
      
      else if (!(neste.hentElement().equals(element)) && (neste.hentHøyre() != null))
         neste = finnIgjen( element, neste.hentHøyre());
      
      return neste;
   }
   
  /*******************************************************************************
     Returnerer ein referanse til det spesifiserte elementet hvis det finst
     i dette BS-treet, null elles. Bruk av rekursjon
  / ******************************************************************************/
   public T finn1 (T element) {
   // Søk med rekursiv hjelpemetode 
      
      return finnRek(element, rot);
   }
   
  // Den rekursive hjelpemetoden for søking
   private T finnRek(T element, BinærTreNode<T> p){
      T svar = null;
      if (p!=null){
         if(element.compareTo(p.hentElement())==0){	// I rot
         	svar = p.hentElement();
         } else if (element.compareTo(p.hentElement())<0) {
         	svar = finnRek(element, p.hentVenstre());				// I venstre u.t.
         } else {
         	svar = finnRek(element, p.hentHøyre()) ;					// I høgre u.t.
         }
      }
   	  return svar;
   }


   /******************************************************************
     Returnerer ein referanse til det spesifiserte elementet hvis det finst
     i dette BS-treet, null elles. Ikkje bruk av rekursjon.
  / ******************************************************************/
   public T finn2 (T element) {
   // Søk med while-setning
   
      BinærTreNode<T> p = rot;
     T svar = null;
      while(p!=null && svar==null){
      	 if(element.compareTo(p.hentElement())<0)
      	 	 p = p.hentVenstre();
      	 else if(element.compareTo(p.hentElement())>0)
      	 	 p = p.hentHøyre();
      	 else
      	 	 svar = p.hentElement(); 	
      }
      return svar;
   }
      
   //*****************************************************************
   // Gjennomgår treet i preorden
   //*****************************************************************
   
   	public void visPreorden(){
		visRekPreorden(rot);
		System.out.println();
	}
	
	private void visRekPreorden(BinærTreNode<T> p){
		if (p!=null){
			System.out.print(p.hentElement()+ " ");
			visRekPreorden(p.hentVenstre());
			visRekPreorden(p.hentHøyre());
		}
	}
	
   //*****************************************************************
   // Gjennomgår treet i inorden
   //*****************************************************************
   	
	public void visInorden(){
		visRekInorden(rot);
		System.out.println();
	}
	
	private void visRekInorden(BinærTreNode<T> p){
		if (p!=null){
			visRekInorden(p.hentVenstre());
			System.out.print(p.hentElement()+ " ");
			visRekInorden(p.hentHøyre());
		}
	}
     
   
}//class

//************************************************************************
//************************************************************************

class TestBSTre{
	public static void main(String[]a){
		//Lagar BS-tre med 8 nodar
		//Skriv ut i in-orden, dvs sortert
		//Testar om veriden 10 er i treet
		//
		
		final int ANTAL_NODAR = 16;
		Random tilfeldig = new Random();
		
		KjedetBinærSøkeTre <Integer>bs = new KjedetBinærSøkeTre<Integer>();
		Integer resultat = null;
		
		for(int i = 0; i < ANTAL_NODAR; i++){
			Integer element = new Integer(tilfeldig.nextInt(30));
			bs.leggTilElement(element);
		}
		
		System.out.println("Treet med  " + ANTAL_NODAR + " nodar.");
		
		bs.visInorden();
		
		Integer el = new Integer(10);
		
		//************************************************************************
		
		resultat = bs.finn(el);
		if(resultat != null)
				System.out.println("\nSoekte etter " + el +" og fann "+resultat);
	 	else
		        System.out.println("\nSoekte etter " + el +" som ikkje var i treet "); 		
		
		//****************************************************************************
	
		resultat = bs.fjernMaks();
		if(resultat != null)
			 	System.out.println("\nFjerna stoerste " + resultat );
		else
		       System.out.println("Treet er tomt");	 	
		System.out.println("Treet er no: ");
		bs.visInorden();
		
		//****************************************************************************
		resultat = bs.fjernMin();
		if(resultat != null)
		       System.out.println("\nFjerna minste " + resultat);
		 else
		     System.out.println("Tree er tomt ");
		 System.out.println("Treet er no: ");    
		 bs.visInorden();
		 //****************************************************************************
		 		     
		resultat = bs.finnMin();
		if(resultat != null)
		      System.out.println("\nMinste element " + resultat);
		else
		   System.out.println("Treet er tomt");
		
		//******************************************************************************
		    	
		resultat = bs.finnMaks();
		if(resultat != null)
		     System.out.println("\nStoerste element " + resultat);
		else
		   System.out.println("Treet er tomt");     
		     
		//****************************************************************************

		
	}
}//class